Build a Lua Interpreter in Rust

https://wubingzheng.github.io/build-lua-in-rust/en/

RustでLuaのインタプリタを実装するチュートリアル

原本は中国語で、それを英語に機械翻訳している

1. hello world!

概観の解説

プログラムの実行にはソースコードをcomputer-excutableな言語に翻訳する工程が必要である

翻訳のタイミングによって大まかに2種類に分けられる

コンパイラ

ソースコードからコンピュータが直接実行可能なファイルを生成する

インタプリタ

ソースコードをリアルタイムでパースし、事前にコンパイルされたサブルーチンに割り当てる

サブルーチン: ひとまとまりの処理

関数、サブルーチン、コンポーネント…似た文脈と意味で使われている言葉多くない？

パース・実行モデル

文字ストリーム→(字句解析)→トークンストリーム→(構文解析)→構文木→(意味解析)→中間コード

中間コードはバイトコードとも呼ばれる

中間コードはVMによって実行される

パース(ソースコード→中間コード)と実行(VM)の2段階に分けられる

あくまで一般的なモデルである

例: Lua公式実装は構文木を作らない

今回実装するインタプリタもモデルの一部工程を省略

文字ストリーム→(字句解析)→トークンストリーム→(構文解析)→バイトコード←(実行)←VM

バイトコード

luac

Luaのソースコードから中間コードを生成するコンパイラ

code: shell

$ luac -l hello_world.lua

main <hello_world.lua:0,0> (5 instructions at 0x600000d78080)

0+ params, 2 slots, 1 upvalue, 0 locals, 2 constants, 0 functions

1 1 VARARGPREP 0

2 1 GETTABUP 0 0 0 ; _ENV "print"

3 1 LOADK 1 1 ; "hello, world!"

4 1 CALL 0 2 1 ; 1 in 0 out

5 1 RETURN 0 1 1 ; 0 out

GETTABUP

グローバル変数をスタックへロードする

パラメータ1: スタックのindex(0)

パラメータ2: 無視

パラメータ3: 定数テーブルのindex(0) (?)

グローバル変数名"print”

複雑なのでこれは一時的な説明らしい

LOADK

定数をスタックにロードする

パラメータ1: スタックのindex(1)

パラメータ2: 定数テーブルのindex(1)

定数名"hello, world!"

CALL

関数呼び出し

パラメータ1: 関数のスタックindex(0)

code: 実行中のスタックダイアグラム

+-----------------+

0 | print | <- function

+-----------------+

1 | "hello, world!" |

+-----------------+

| |

Luaの言語仕様にバイトコードの記載はなく、あくまで"詳細な実装"の範疇

実装によってバイトコードが全く異なる

Lua公式

32bit符号なし整数

前半7bitがコマンド、後半25bitがパラメータ

5種類のフォーマットがある

それぞれパラメータが異なる

ビット演算？

LuaJIT

32bit符号なし整数

2種類のフォーマット

公式に比べてかなりシンプル

C言語のマッチング構造体とユニオンを利用している

ビット演算を回避

バイトコードをより便利に構築・解析

我々の実装

Rustのenumを使う

code: rust

#derive(Debug)

pub enum ByteCode {

GetGlobal(u8, u8),

LoadConst(u8, u8),

Call(u8, u8),

}

Rust's enum is really nice!(原文ママ)

値と型

定数/変数と値の関係を保持するテーブルが必要

定数テーブル

インデックスで参照

Vecで実装

グローバル変数テーブル

名前で参照

HashMap<String, Value>で実装

Luaは動的型付け

型は変数ではなく値に束縛される

逆に静的型付けでは変数に束縛される

code: L:Lua, R:Rust

variable values variable values

+---------+ +---------------+ +---------------+ +-----------+

+---------+ | | value: 10 | | type: Integer | | +-----------+

| +---------------+ +---------------+ X

| |

| +----------------+ | +----------------+

\-->| type: String | \-->| value: "hello" |

| value: "hello" | +----------------+

+----------------+

dynamic type static type

"type" is bound to values "type" is bound to variables